package th.retrofit.lib;

/**
 * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *
 */
public class Solution114 {
    public void flatten(TreeNode root) {
        if (root == null) return;
        dfs(root);
    }

    public TreeNode dfs(TreeNode root) {
        if (root.left == null && root.right == null) return root;
        TreeNode temp = root.right;
        TreeNode tail = null;
        if (root.left != null) {
            tail = dfs(root.left);
            root.right = root.left;
            root.left = null;
        }
        if (temp != null) {
            TreeNode node = dfs(temp);
            if (tail != null) {
                tail.right = temp;
            }
            tail = node;
        }
        return tail;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.array2Tree(1);
        new Solution114().flatten(root);
        System.out.println(root);
    }
}
